package com.ljy.my_study.lintcode.最少划分子串;
/** 
* @author James
* @date 2019年2月2日 
*/
public class TestMain {
//	描述
//	给定一个包含n个小写字母的字符串s，要求将字符串划分成若干个连续子串，子串中的字母类型相同，同时子串的字母个数不超过k，输出最少划分的子串数量。
//
//	n \leq 1e5n≤1e5
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给定 s = "aabbbc", k = 2, 返回4
//
//	解释：
//	划分成 "aa", "bb", "b", "c" 四个子串
//	给定 s = "aabbbc", k = 3, 返回3
//
//	解释：
//	划分成 "aa", "bbb", "c" 三个子串
	public static void main(String[] args) {
		System.out.println(getAns("aabbbc",4));
	}
	
	public static int getAns(String s, int k) {
//		char[] charArr=s.toCharArray();
		int count=0;
		int sum=0;
		Character c=null;
		for(int i=0;i<s.length();i++) {
			count++;
			
			if(!(c!=null&&c==s.charAt(i)&&count<=k)) {
				count=0;
				c=null;
			}
			if(c==null) {
				c=s.charAt(i);
				count++;
				sum++;
			}
		}	
		return sum;
    }
}
